%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass{article}

\usepackage{subfigure}
\usepackage{tikz}
\usetikzlibrary{external}
\tikzexternalize{grid-graph-spanning-trees}

\begin{document}

\begin{figure}
\subfigure[]{
\begin{tikzpicture}
[darkline/.style={line width=2.5pt},%
  lightline/.style={-,ultra thick,color=gray!30}]
%% set up the grid
\foreach \xstart/\xend/\y in {0/4.5/0, 0/4.5/1.5, 0/4.5/3, 0/4.5/4.5} {
  \draw[lightline] (\xstart,\y) -- (\xend,\y);
  \draw[lightline] (\y,\xstart) -- (\y,\xend);
}
%% draw the spanning tree
\draw[darkline] (0,1.5) -- (0,0) -- (4.5,0);
\draw[darkline] (1.5,0) -- (1.5,1.5) -- (4.5,1.5) -- (4.5,3) --
  (0,3) -- (0,4.5);
\draw[darkline] (1.5,3) -- (1.5,4.5);
\draw[darkline] (3,3) -- (3,4.5) -- (4.5,4.5);
\end{tikzpicture}
}
%%
%%
\qquad
\subfigure[]{
\begin{tikzpicture}
[darkline/.style={line width=2.5pt},%
  lightline/.style={-,ultra thick,color=gray!30}]
\foreach \xstart/\xend/\y in {0/4.5/0, 0/4.5/1.5, 0/4.5/3, 0/4.5/4.5} {
  \draw[lightline] (\xstart,\y) -- (\xend,\y);
  \draw[lightline] (\y,\xstart) -- (\y,\xend);
}
%% draw the spanning tree
\draw[darkline] (4.5,1.5) -- (4.5,0) -- (0,0) -- (0,1.5) -- (1.5,1.5)
  -- (1.5,3);
\draw[darkline] (0,4.5) -- (4.5,4.5) -- (4.5,3) -- (0,3);
\draw[darkline] (3,1.5) -- (3,3);
\end{tikzpicture}
}
\end{figure}

\end{document}
